
\subsubsection{Instancias de testeo}

El conjunto de instancias para testear fue elegido variando los valores para n, la cantidad de joyas,para cada uno fue definido de manera aleatoria los costos y tiempos de las joyas. 

La complejidad del algoritmo como se demostro en la seccion de complejidad estaba delimitado por el merge sort, por eso se utilizan numeros aleatorios en cuanto a la entrada y a los valores de cada una.


\subsubsection{Resultados experimentales}

Realizamos una experimentación para medir la performance del algoritmo de 1000 ejecuciones variando el tamaño de la entrada(n) entre 1 y 100000, usando una secuencia de n joyas aleatorios en cada ejecución, a su vez era aleatoria el costo y tiempo en valores entre 1 y 10000. Para cada ejecución medimos el tiempo en milisegundos que toma completar el algoritmo. Los resultados que obtuvimos se pueden ver en el siguiente gráfico:

\includegraphics[scale=0.7]{ej2.png}

Como se puede ver, los resultados del experimento se aproximan a la complejidad calculada(n*log(n)).
Esto es esperado ya que el merge sort es lo que termina dando la complejidad al algoritmo, el cual en caso promedio y peor caso es O(n*log(n)), ya que las otras operaciones que no corresponden al merge sort son de orden lineal. A su vez, por esa misma razón, no hay un conjunto de entradas que puedan ser consideradas un peor caso, ya que el merge sort no lo tiene. De modo que variar el orden de las joyas, tiempos y costos no acarrea ninguna diferencia en cuanto a los resultados de las distintas ejecuciones.
